1. Field of the Invention
The present invention relates generally to multithreaded computing systems and methods. More particularly, the present invention relates to systems and methods of scheduling computing threads for processing in a multithreaded computing system.
2. Background Art
One type of multithreaded computing system includes a thread scheduler that schedules computing threads. Once a thread is scheduled, an instruction of the scheduled thread can issue to a pipelined processor for processing. The pipelined processor includes a sequence of stages, each of which performs a different operation on an instruction as the instruction sequences through the stages. Moreover, the pipelined processor can process multiple instructions at the same time, each of the instructions being in a different stage.
Maintaining a high throughput of the pipelined processor in this type of computing system generally depends upon scheduling a runnable thread during a scheduling cycle, and issuing an instruction of the scheduled thread to the first stage of the pipelined processor during the next scheduling cycle. Stated differently, the throughput of the pipelined processor is generally higher when each stage of the pipelined processor contains an instruction.
In some multithreaded computing systems, a runnable thread may become unrunnable after the thread scheduler schedules the thread but before an instruction of the scheduled thread is issued to the pipelined processor. This can occur, for example, when a thread is scheduled during a scheduling cycle, and a previously issued instruction of that thread causes the computing system to initiate a thread context switch. The thread context switch occurs during the next scheduling cycle. During this next scheduling cycle, however, an additional instruction of the scheduled thread is not issued to the pipelined processor because the scheduled thread is now unrunnable. Instead, another runnable thread is scheduled during this next scheduling cycle, and an instruction of this other thread issues to the pipelined processor in the following scheduling cycle. Accordingly, no instruction is issued to the pipelined processor during the scheduling cycle in which the thread context switch occurs. Consequently, the first stage of the pipelined processor becomes empty and thus the throughput of the pipelined processor is diminished.
In light of the above, there exists a need to improve thread scheduling in a way that avoids empty stages in a pipelined processor.